package leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-13 16:36
 **/
public class LeetCode621 {

    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> freq = new HashMap<Character, Integer>();
        // 最多的执行次数
        int maxExec = 0;
        for (char ch : tasks) {
            int count = freq.getOrDefault(ch, 0) + 1;
            freq.put(ch, count);
            maxExec = Math.max(maxExec, count);
        }

        // 具有最多执行次数的任务数量
        int maxCount = 0;
        Set<Map.Entry<Character, Integer>> entrySet = freq.entrySet();
        for (Map.Entry<Character, Integer> entry : entrySet) {
            int value = entry.getValue();
            if (value == maxExec) {
                ++maxCount;
            }
        }

        //如果maxCount <= n + 1,那么最大值为(maxExec - 1) * (n + 1), 如果maxCount > n + 1,说明达到maxExec次数的任务大于n + 1,说明最好情况下cpu不会有待命状态,此时最少时间就是任务数
        return Math.max((maxExec - 1) * (n + 1) + maxCount, tasks.length);
    }


}
